/**
 * @author ChaP
 * @date 2019/06/17
 * @describe:
 */
package CodingTest.AC20190617;

/**
 * leetcode - 498
 * 给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。

  

 示例:

 输入:
 [
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
 ]

 输出:  [1,2,4,7,5,3,6,8,9]

 */
public class findDiagonalOrder {
    public int[] findDiagonalOrder(int[][] matrix){
        if(matrix.length == 0) return new int[]{};
        int rows = matrix.length;
        int cols = matrix[0].length;
        int [] res = new int[rows * cols];
        int r = 0, c= 0;
        for(int i = 0;i<res.length;i++){
            res[i] = matrix[r][c];
            //r 为行，c为列
            //r+c为遍历的层数，偶数向上遍历，奇数向下遍历
            if((r+c)%2==0){
                if(c == cols-1){
                    // 往右移一格准备向下遍历
                    r++;
                }else if(r == 0){
                    // 往下移动一格准备向下遍历
                    c++;
                }else {
                    // 往上移动
                    r--;
                    c++;
                }
            }else{
                if(r == rows-1){
                    //往右移动一格准备向上遍历
                    c++;
                }else if(c == 0){
                    //往上移动一格准备向上遍历
                    r++;
                }else{
                    // 往下移动
                    r++;
                    c--;
                }
            }

        }
        return res;
    }

    public static void main(String[] args) {
        int[][] m = {{1,2,3},{4,5,6},{7,8,9}};
        findDiagonalOrder d = new findDiagonalOrder();
        int [] r = d.findDiagonalOrder(m);
        System.out.println(r);
    }
}
